Prywatna historia kobiety legendy. Uparta i ambitna. Zawsze w centrum wydarzeń, w centrum polskiej historii. Tam, gdzie czuje się ważna. "Przodująca spawaczka", "Bohaterka Sierpnia ’80", "Symbol Solidarności". Rok 1943, na Wołyniu trwa rzeź. Urodzona w ukraińskiej rodzinie Anna ma kilkanaście lat. Jest na służbie u Polaków, gdy dociera do niej wiadomość, że wszyscy jej najbliżsi zginęli. Musi uciekać, a w nowej rzeczywistości poradzić sobie sama. Ukrywa swoją tożsamość: zdobywa fałszywą metrykę, zmienia wyznanie. Liczy, że prawdy o niej nie odkryje nikt. Rok 1950, Stocznia Gdańska szuka spawaczy. Anna zgłasza się na kurs, chce być najlepsza. Już wkrótce o jej wzorowej pracy dla Polski Ludowej napiszą gazety. Rok 1980, rodzi się "Solidarność". Zwolnienie Anny z pracy wywołuje strajk w stoczni, do protestu przyłączają się setki zakładów pracy. Z przykładnej działaczki staje się dla partii wrogiem numer jeden. Jej upór i ambicja wkrótce dadzą się we znaki wszystkim. Życie prywatne Anny skrywa wiele tajemnic. Nie opowiada o tym, co przeżyła w czasie wojny. Ucieka od rodziny, która zabrała ją z Wołynia. Będąc w ciąży, rozstaje się z ojcem dziecka. Nikomu, nawet synowi, nie zdradzi jego tożsamości. Szczęśliwe małżeństwo z Kazimierzem kończy przedwczesna śmierć męża. Przez dużą część życia Anna toczy walkę z nowotworem. Dorota Karaś i Marek Sterlingow dotarli do nigdy nie publikowanych archiwalnych nagrań i dokumentów. Odwiedzili rodzinę Anny w Ukrainie, skłonili do zwierzeń jej syna, Janusza Walentynowicza. Rozmawiali z przyjaciółmi i przeciwnikami Anny: Lechem Wałęsą, Bogdanem Borusewiczem, Hanną Krall, Krzysztofem 2, agentem, który zaważył na relacjach Anny z Wałęsą. Przeczytali w IPN-ie teczki związane z opozycją. "Walentynowicz. Anna szuka raju" to nie tylko rzetelne biograficzne śledztwo, ale wciągająca opowieść o kobiecie, której życie było nierozerwalnie związane z najważniejszymi wydarzeniami w powojennej Polsce.